#include <iostream>
#include <cstring>

void BubblSort(int *a, int n)
{
    bool IsSort = false;
    for (int i = n; i >= 0; i--)
    {
        for (int j = 0; j < i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                IsSort = true;
                std::swap(a[j], a[j + 1]);
            }
        }
        if (IsSort == false)
            break;
    }
}

void InsertSort(int *a, int n)
{
    // 多趟排序
    for (int i = 1; i < n; i++)
    {
        // 单趟排序
        int end = i - 1;
        int temp = a[end + 1];
        while (end >= 0)
        {
            if (temp < a[end])
            {
                // 挪动
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = temp;
    }
}

void ShellSort(int *a, int n)
{
    // gap越大 跳动越快  数组越无序 gap越小 数组越有序
    int gap = n;
    while (gap >= 1) // gap>1 预排序 gap=1插入排序
    {
        gap /= 2;
        // 多组排序
        for (int i = 0; i < n - gap; i++)
        {
            // 组内的多次交换
            int end = i;
            int temp = a[i + gap];
            while (end >= 0)
            {
                if (temp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }

            a[end + gap] = temp;
        }
    }
}

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void SelectSort(int *a, int n)
{
    int left = 0, right = n - 1;
    while (left < right)
    {
        int mindex = left, maxdex = left;
        for (int i = left + 1; i <= right; i++)
        {
            if (a[mindex] > a[i])
            {
                mindex = i;
            }
            if (a[maxdex] < a[i])
            {
                maxdex = i;
            }
        }
        swap(&a[left], &a[mindex]);
        if (left == maxdex)
        {
            maxdex = mindex;
        }
        swap(&a[right], &a[maxdex]);
        right--;
        left++;
    }
}

// 堆的向上调整
void AdjustUp(int *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// 堆的向下调整
void AdjustDown(int *a, int n, int parent)
{
    int child = parent * 2 + 1;
    // 找左右孩子中最大的那一个进行比较

    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

// 建大堆
void heapsort(int *a, int n)
{
    // 向下调整建堆 N
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // 向下调整，排序调堆  N*logN
    int end = n - 1;
    while (end > 0)
    {
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        end--;
    }
}

// 归并排序
void _MegerSort(int *a, int left, int right, int *temp)
{
    if (left >= right)
    {
        return;
    }

    int mid = left + (right - left) / 2;
    _MegerSort(a, left, mid, temp);
    _MegerSort(a, mid + 1, right, temp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] > a[begin2])
        {
            temp[i++] = a[begin2++];
        }
        else
        {
            temp[i++] = a[begin1++];
        }
    }

    while (begin1 <= end1)
    {
        temp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        temp[i++] = a[begin2++];
    }

    memcpy(a + left, temp + left, sizeof(int) * (right - left + 1));
}

// 快速排序
int GetMidNumi(int *a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[right] > a[left])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[right] > a[mid])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

void QuickSort1(int *a, int left, int right)
{
    if (left >= right)
    {
        return;
    }

    // 三数取中
    int begin = left, end = right;
    int mid = GetMidNumi(a, left, right);
    if (mid != left)
        swap(&a[left], &a[mid]);
    int keyi = left;

    while (left < right)
    {
        // 右边找小
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        // 左边找大
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }

        // 交换
        swap(&a[left], &a[right]);
    }

    // 交换key和left
    swap(&a[keyi], &a[left]);
    keyi = left;

    // 递归左右两边子序列
    QuickSort1(a, 0, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

void QuickSort2(int *a, int left, int right)
{
    if (left >= right)
    {
        return;
    }

    // 三数取中
    int begin = left, end = right;
    int mid = GetMidNumi(a, left, right);
    if (mid != left)
        swap(&a[left], &a[mid]);

    int temp = a[left];
    int hole = left;

    while (left < right)
    {
        // 右边找小
        while (left < right && a[right] >= temp)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;

        // 左边找大
        while (left < right && a[left] <= temp)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }

    a[hole] = temp;
    // 递归左右子序列
    QuickSort2(a, begin, hole - 1);
    QuickSort2(a, hole + 1, end);
}

// 前后指针法
void QuickSort3(int *a, int left, int right)
{
    // 递归条件
    if (left >= right)
    {
        return;
    }

    int begin = left;
    int end = right;

    // 三数取中
    int mid = GetMidNumi(a, left, right);
    if (mid != left)
        swap(&a[left], &a[mid]);

    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        /*if (a[cur] < a[keyi])
        {
            prev++;
            Swap(&a[prev], &a[cur]);
            cur++;
        }
        else
        {
            cur++;
        }*/

        if (a[cur] < a[keyi] && (prev++) != cur)
            swap(&a[cur], &a[prev]);
        cur++;
    }
    swap(&a[prev], &a[keyi]);

    // 小区间优化——小区间使用直接插入排序
    if ((right - left + 1) < 10)
    {
        // 递归左右子序列
        QuickSort3(a, begin, prev - 1);
        QuickSort3(a, prev + 1, end);
    }
    else
    {
        InsertSort(a + left, right - left + 1);
    }
}

// 三路划分
void QuickSort(int *a, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    if ((right - left + 1) < 10)
    {
        InsertSort(a + left, right - left + 1);
    }

    int begin = left, end = right;
    int mid = GetMidNumi(a, left, right);
    if (mid != left)
        swap(&a[left], &a[mid]);
    int key = a[left];

    int cur = left + 1;

    while (cur <= end)
    {
        if (a[cur] < key)
        {
            swap(&a[cur], &a[begin]);
            cur++;
            begin++;
        }
        else if (a[cur] > key)
        {
            swap(&a[cur], &a[end]);
            end--;
        }
        else
        {
            cur++;
        }
    }

    QuickSort(a, left, begin - 1);
    QuickSort(a, end + 1, right);
}

int main()
{
    int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int a1[10] = {8, 6, 5, 2, 3, 1, 7, 9, 0, 4};
    int a2[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // BubblSort(a2,10);
    // InsertSort(a1, 10);
    // ShellSort(a1, 10);
    // heapsort(a1, 10);
    // SelectSort(a1, 10);
    // int temp[10] = {0};
    // _MegerSort(a1, 0, 9, temp);
    QuickSort(a1, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        std::cout << a1[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}